Ketika usaha Tentera di Florida terbukti kurang berjaya, ia beralih kearah kaedah baru, dengan menggunakan anjing perburuan bloodhound bagi menjejak Seminole. Sungguhpun Jeneral Taylor telah memohon dan menerima kebenaran bagi mendapatkan bloodhounds pada tahun 1838, dia tidak melakukannya. Kerajaan jajahan Florida membeli sekawanan bloodhound dari Cuba pada awal 1840 dan menggaji pengendali anjing dari Cuba. Semasa ujian awal anjing perburuan memberikan hasil bercampur-campur, bangkangan dari orang awam di Amerika Syarikat meletus mengenai kebimbangan anjing sedemikian akan cuba membunuh atau mencacatkan Seminole, termasuk wanita dan kanak-kanak. Setiausaha Tentera terpaksa mengeluarkan arahan agar anjing diikat mulut semasa digunakan bagi menjejak. Ketika ia berkembang, oleh kerana anjing bloodhound tidak mampu menjejak menerusi air, puak Seminole dengan mudah mengelakkan mereka.[50]

Di utara Florida, rumah sekatan Taylor dan system rondaan mengekalkan Seminole bergerak, tetapi tidak mampu menghalau mereka dari kawasan tersebut. Serangan hendap ke atas pengembara sering berlaku. Pada 13 Februari 1840 koc surat antara St. Augustine dan Jacksonville diserang hendap. Pada May Seminole menyerang kumpulan pelakon berhampiran St. Augustine, membunuh sejumlah enam orang. Pada bulan yang sama sekumpulan empat orang tehtera mengembara antara kubu-kubu di County Alachua diserang, dengan seorang terbunuh dan dua lagi tidak kembali. Satu kumpulan lapan belas orang mengejar pihak Indian, tetapi enam dari mereka terbunuh.[51]

Pada May 1840 Zachary Taylor, setelah berkhidmat lebih lama dari sebarang komander dalam perang Florida sebelumnya, diluluskan permohonannya untuk pertukaran. Dia digantikan oleh Brig. Jen. Walker Keith Armistead, yang sebelumnya berkhidmat di Florida sebagai pembantu Jen. Jesup. Armistead segera menyerang, menghantar 100 tentera setiap kali bagi memburu Seminole dan kem mereka. Bagi kali pertama, pihak Tentera secara aktif berkempen di Florida semasa musim panas, menawan dan memusnahkan tanaman dan bangunan. Pihak Seminole juga kekal aktif. Sejumlah empat belas tentera terbunuh dalam perkhidmatan dalam bulan Julai.[52] Pihak Tentera kini memburu kem tersembunyi Seminole, membakar ladang dan menghalau kuda, lembu dan babi.[53]

Armistead bercadang menyerahkan pertahanan Florida utara dari Fort King kepada pasukan bersenjata awam dan sukarelawan, sementara Tentera biasa bertugam menghadkan Seminoles ke selatan Fort King, dan mengejar mereka dengan tekun. Kem dan ladang tersembunyi dijumpai dan dimusnahkan sepanjang tengah Florida, dan menjelang pertengahan musim panas pihak Tentera telah memusnahkan 500 ekar (2.0 km2) tanaman Seminole. Jeneral Armistead menjadi terasing dari kerajaan jajahan, sungguhpun dia memerlukan 1,500 pasukan bersenjata awam dari jajahan bagi mempertahankan kawasan di utara Fort King. Bagi memperkukuhkan usaha di selatan Fort King, Regimen Infantri ke-8 dihantar ke Florida. Tentera di Florida kini termasuk sepuluh kompeni Second Dragoon, sembilan kompeni Artileri KeTiga, dan Regimen Infantri Pertama, Regimen Infantri Kedua, dan Regimen Infantri Ketiga, Regimen Infantri Keenam, Regimen Infantri Ketujuh dan Regimen Infantri Kelapan.[54]

Perubahan juga berlaku di selatan Florida. Di Fort Bankhead yang terletak di Key Biscayne Kol. Harney melaksanakan program latihan pesat perperangan di paya dan hutan bagi orang-orangnya.[55] Tentera laut memainkan peranan lebih besar dalam perang, dengan kelasi dan marin mudek sungai dan anak sungai, dan ke dalam Everglades.[56]